#include "BinaryTree.h"
#include "Queue.h"

BTNode* BuyBTNode(BTDataType x)
{
	BTNode* root = (BTNode*)malloc(sizeof(BTNode));
	if (NULL == root)
	{
		perror("malloc fail:");
		return NULL;
	}
	root->data = x;
	root->left = root->right = NULL;

	return root;
}
// 通过前序遍历的数组"ABD##E#H##CF##G##"构建二叉树
BTNode* BinaryTreeCreate(BTDataType* a, int* pi)
{
	if (a[*pi] == NULL)
	{
		(*pi)++;
		return NULL;
	}

	BTNode* root = BuyBTNode(a[*pi]);
	(*pi)++;
	root->left = BinaryTreeCreate(a, pi);
	root->right = BinaryTreeCreate(a, pi);

	return root;
}
// 二叉树销毁
void BinaryTreeDestory(BTNode* root)
{
	if (NULL == root)
		return;

	//后序遍历更优
	BinaryTreeDestory(root->left);
	BinaryTreeDestory(root->right);
	free(root);
}
// 二叉树节点个数
int BinaryTreeSize(BTNode* root)
{
	if (NULL == root)
		return 0;

	//分治算法
	return BinaryTreeSize(root->left)
		+ BinaryTreeSize(root->right) + 1;
	//简化
	//return root == NULL ? 0 : BinaryTreeSize(root->left)
	//						+ BinaryTreeSize(root->right) + 1;//简化代码
}
// 二叉树叶子节点个数
int BinaryTreeLeafSize(BTNode* root)
{
	if (NULL == root)
		return 0;

	if (NULL == root->left && NULL == root->right)
		return 1;

	return BinaryTreeLeafSize(root->left)
		+ BinaryTreeLeafSize(root->right);
}
//二叉树的高度
int BTreeHeight(BTNode* root)
{
	if (NULL == root)
		return 0;

	int leftH = BTreeHeight(root->left);
	int rightH = BTreeHeight(root->right);

	return leftH > rightH ? leftH + 1 : rightH + 1;
}
// 二叉树第k层节点个数
int BinaryTreeLevelKSize(BTNode* root, int k)
{
	assert(k > 0);

	if (NULL == root)
		return 0;

	if (1 == k)
		return 1;

	return BinaryTreeLevelKSize(root->left, k - 1)
		+ BinaryTreeLevelKSize(root->right, k - 1);
}
// 二叉树查找值为x的节点
BTNode* BinaryTreeFind(BTNode* root, BTDataType x)
{
	if (NULL == root)
		return NULL;

	if (root->data == x)
		return root;
	
	BTNode* ret1 = BinaryTreeFind(root->left, x);
	if(ret1)
		return ret1;

	BTNode* ret2 = BinaryTreeFind(root->right, x);
	if(ret2)
		return ret2;

	return NULL;
}
// 二叉树前序遍历 
void BinaryTreePrevOrder(BTNode* root)
{
	if (NULL == root)
	{
		printf("N ");
		return;
	}

	printf("%c ", root->data);
	BinaryTreePrevOrder(root->left);
	BinaryTreePrevOrder(root->right);
}
// 二叉树中序遍历
void BinaryTreeInOrder(BTNode* root)
{
	if (NULL == root)
	{
		printf("N ");
		return;
	}

	BinaryTreeInOrder(root->left);
	printf("%c ", root->data);
	BinaryTreeInOrder(root->right);
}
// 二叉树后序遍历
void BinaryTreePostOrder(BTNode* root)
{
	if (NULL == root)
	{
		printf("N ");
		return;
	}

	BinaryTreePostOrder(root->left);
	BinaryTreePostOrder(root->right);
	printf("%c ", root->data);
}
// 层序遍历
void BinaryTreeLevelOrder(BTNode* root)
{
	Queue q;
	QueueInit(&q);

	if (root)
		QueuePush(&q, root);

	while (!QueueEmpty(&q))
	{
		BTNode* front = QueueFront(&q);//先将队头元素记下来
		QueuePop(&q);
		printf("%c ", front->data);

		if (front->left)
			QueuePush(&q, front->left);
		if (front->right)
			QueuePush(&q, front->right);
	}

	QueueDestroy(&q);
}
// 判断二叉树是否是完全二叉树
bool BinaryTreeComplete(BTNode* root)
{
	assert(root);

	Queue q;
	QueueInit(&q);

	if (root)
		QueuePush(&q, root);
	
	while (!QueueEmpty(&q))
	{
		BTNode* front = QueueFront(&q);
		QueuePop(&q);

		//为空就跳出
		if (NULL == front)
			break;
		
		QueuePush(&q, front->left);
		QueuePush(&q, front->right);
	}
	
	//检查队列中剩下的节点有没有非空
	while (!QueueEmpty(&q))
	{
		BTNode* front = QueueFront(&q);
		QueuePop(&q);

		//遇见非空就说明不是完全二叉树
		if (front)
		{
			QueueDestroy(&q);
			return false;
		}
	}

	QueueDestroy(&q);
	return true;
}
